W6. Deterministic Pushdown Automata

1. Theory

1.1 From Finite Automata to Pushdown Automata

We already know that Finite State Automata (FSAs) can recognize regular languages. But FSAs have a fundamental limitation: they have only a fixed, finite amount of memory — precisely the current state. This makes certain languages impossible to recognize, such as , where the machine would need to remember an arbitrarily large count of ’s.

To go beyond regular languages, we need a model with more memory. The natural extension is to attach a stack to an FSA, producing a Pushdown Automaton (PDA). The name “pushdown” refers to the push-down nature of the stack, where new items are placed on top and the top item is always the one removed first.

From FSA to PDA: the same finite control gains an unbounded stack

Informally:

• FSA = finite control unit (states only)
• PDA = finite control unit + an infinite stack

The hierarchy of computational models, from weakest to most powerful, looks like:

• Combinational logic — no memory
• Finite State Automata — fixed, bounded memory (current state only)
• Pushdown Automata — unbounded stack memory (can grow without limit)
• Turing Machines — full read/write tape (most powerful)

PDAs sit exactly at the level above FSAs and can recognize context-free languages (CFLs), which include most programming language constructs. This is why PDAs are at the heart of compilers — the syntax of programming languages is context-free.

1.2 The Stack: A Refresher

A stack is a last-in, first-out (LIFO) data structure. Think of a stack of trays in a cafeteria: you can only add or remove from the top.

LIFO stack discipline used by PDAs

Operations:

• Push: Place a new symbol on top of the stack.
• Pop: Remove the top symbol from the stack (and “read” it at the same time).

A PDA’s stack starts with a special bottom-of-stack symbol , which serves as a sentinel marking the bottom. When is on top, the stack is effectively empty.

Example — push , , , then pop:

1. Initial stack: (bottom only)
2. Push : stack = (top to bottom)
3. Push : stack =
4. Push : stack =
5. Pop: removes ; stack =

The most recently pushed symbol is always the first to be removed. This LIFO property makes the stack ideal for matching nested structures like balanced parentheses.

Historical note: The concept of a stack was introduced by Alan Turing in his 1946 paper on the Automatic Computing Engine (ACE), where he called the operations BURY and UNBURY, and used them in the theory of subroutines.

1.3 Informal Description of a PDA

A PDA has three components:

1. An input tape — a read-only, left-to-right sequence of symbols (the input string)
2. A finite control unit — like an FSA, it keeps track of the current state
3. A stack of infinite size — the extra memory; the control unit reads the top and replaces it

PDA step: read input, inspect the stack top, then move to a new configuration

In each step, a PDA looks at three things simultaneously:

• The current state
• The next input symbol (or for a “silent” move)
• The top of the stack

Based on these three inputs, it:

1. Moves to a new state
2. Advances the input head (or stays in place for -moves)
3. Replaces the top stack symbol with some string

Using the stack, a PDA can:

• Push symbols onto the stack (replace top with , so is now on top)
• Pop the top symbol (replace top with , i.e., nothing)
• Leave the stack unchanged (replace top with )
• Make -moves — transitions that consume no input, only modify the stack

Acceptance criteria: A string is accepted if, after reading it completely, the PDA is in an accepting (final) state. The stack content at the end does not matter for acceptance by final state.

1.4 Formal Definition of a PDA

A Pushdown Automaton is a 7-tuple:

where:

• — finite set of states
• — finite input alphabet (the symbols the PDA reads from its tape)
• — finite stack alphabet (the symbols that can appear on the stack; note and may overlap)
• — the transition function (a partial function mapping to sets of possible outcomes)
• — the initial state
• — the initial stack symbol (bottom-of-stack marker, placed on the stack at the start)
• — the set of accepting (final) states

Reading the transition function: A transition means:

In state , reading input symbol (or ), with stack symbol on top: move to state and replace with the string .

The graphical notation on arrows is: — meaning “read from input, pop from stack, push .”

• To push onto the stack below : write (replace with ; now is on top)
• To pop : write (replace with nothing)
• To leave the stack unchanged: write

Conditions on :

• The stack always contains at least
• is never removed from the stack
• No additional copies of are pushed onto the stack

1.5 Deterministic Pushdown Automata (DPDA)

The general PDA above is nondeterministic: can contain multiple pairs, meaning the PDA can “choose” among several transitions at each step. Nondeterministic PDAs (NPDAs) are powerful tools, but in practice, compilers use deterministic PDAs.

A PDA is a Deterministic Pushdown Automaton (DPDA) if it satisfies both of the following conditions:

1. At most one transition at each step: For every , every , and every , the set has at most one element.
2. No conflict between input and -transitions: For every , every , and every , the two sets and cannot both be non-empty.

The second condition says: if there is an -transition from state with stack top , then there must be no input-reading transition from the same state with the same stack top . This prevents the PDA from having to “choose” between reading input or making a spontaneous move.

Why the -rule matters: If both and were non-empty simultaneously, the PDA would be nondeterministic — it could either consume input symbol or make a spontaneous move. DPDAs forbid this ambiguity.

Practical convention: We typically use as the final transition to an accepting state, after all input has been consumed and the stack holds only .

1.6 Configurations and Transitions

To formally describe the execution of a PDA, we introduce the notion of a configuration.

1.6.1 Configuration

A configuration is a “snapshot” of the PDA at any instant. It captures everything about the current computation:

where:

• — the current state of the control device
• — the unread portion of the input string (the part not yet consumed)
• — the current stack contents (entire stack, from top to bottom)

Convention: The stack is written top-first. If , then is the top of the stack and is everything below.

Example: The configuration means: the PDA is in state , the remaining unread input is , and the stack (top to bottom) contains , , .

Initial configuration: for any input string .

1.6.2 Transitions Between Configurations

The symbol (“yields” or “transitions to”) describes a single step of PDA computation. There are two cases:

Case 1 — Reading an input symbol: If is defined, and the current configuration has on top of the stack and as remaining input, then:

In words: consume the input symbol , pop from the stack, push , move to state .

Case 2 — -move (spontaneous): If is defined, and the current configuration has on top of the stack:

In words: do NOT consume any input, pop from the stack, push , move to state .

The key difference between the two cases: in Case 1, the input head advances by one symbol; in Case 2, the input head stays in place.

1.6.3 Multi-Step Computation:

We define as the reflexive transitive closure of . That is, means there is a sequence of zero or more steps:

The relation captures the complete computation path from one configuration to another.

1.6.4 Acceptance by a PDA

A string is accepted by PDA if:

for some and some .

In plain English: starting from the initial configuration (state , full input , stack containing only ), the PDA can reach a configuration where:

1. The entire input has been consumed (remaining input is )
2. The current state is accepting ()
3. The stack can contain anything ( is arbitrary)

The language recognized by is:

1.7 Two Acceptance Modes

A PDA can accept a string in two different ways:

• Acceptance by final state: The input is completely consumed and the PDA is in a state . The stack content is irrelevant.
• Acceptance by empty stack: The input is completely consumed and the stack contains only (effectively empty). The state does not matter.

For nondeterministic PDAs, these two acceptance modes are equivalent: any language accepted by one mode can be accepted by the other (using a different PDA). For deterministic PDAs, however, the two modes are not equivalent.

A subtlety about empty-stack acceptance: Languages accepted by empty stack must be prefix-free — no string in the language is a proper prefix of another string in the language. Once the stack empties on reading , processing any extension is impossible.

1.8 Worked Example: PDA for

This classic example shows how a PDA uses its stack to count symbols.

Strategy: Push one stack symbol for each in the input. When ’s start appearing, pop one for each . If the stack holds only exactly when all ’s are consumed, the counts matched perfectly.

PDA specification:

• States: (start), (reading ’s), (reading ’s), (accepting)
• Stack alphabet:
• Transitions:

Transition	Notation	Meaning
		Read first ; push on top of
		Read each subsequent ; push another
		Read first ; pop one
		Read each subsequent ; pop one
		Input exhausted; on top means all ’s were matched; accept

Trace for input :

Step	State	Remaining Input	Stack (top first)	Rule Applied
1				: push
2				: push
3				: pop
4				: pop
5				: accept
6				ACCEPT

The full computation is:

1.9 More PDA Examples

1.9.1 PDA for

Strategy: Push one per before the . The single acts as a pivot. After seeing , pop one per on the right side. If the stack reaches exactly at the end of input, the two -blocks are equal.

• States: (start, push phase), (pop phase, after ), (accepting)
• Transitions:

Transition	Notation	Meaning
		First before : push
		Each subsequent before : push
		See the ; keep stack unchanged, change state
		Each after : pop one
		All ’s matched; accept

1.9.2 PDA for

The language consists of strings of the form : a string , a center marker , then reversed. The serves as the “middle pivot.”

Strategy: Push all symbols of onto the stack. When is read, switch to pop mode. For each symbol of , pop the matching symbol from the stack. If the stack reaches after all input, accept.

• States: (push phase), (pop phase, after ), (accepting)
• Key transitions (push phase, state , loops):
  • ; ; ; ; ;
• Pivot (on seeing ): ; ; (all move )
• Pop phase (state , loops): ;
• Accept: (move )

1.9.3 PDA for Balanced Parentheses

The language of balanced (well-formed) parentheses is the prototypical context-free language. Intuitively, each ( must have a matching ) and matched pairs must be properly nested.

• States: (start), (processing), (accepting)
• Transitions:
  • : — first (: push
  • : — each additional (: push
  • : — each ): pop one (matching the ()
  • : — input exhausted, stack empty: accept

1.10 PDAs vs FSAs: The Big Picture

• Every regular language can be recognized by a PDA (just simulate the FSA without using the stack).
• PDAs can recognize languages that no FSA can (e.g., ).
• Therefore, the class of context-free languages strictly contains the class of regular languages.

Classic PDA for aⁿbⁿ

• Regular languages Languages recognized by PDAs (context-free languages)
• Examples of context-free but not regular: , , balanced parentheses
• Examples beyond PDAs: (requires counting three quantities simultaneously — no stack can do this)

Memory perspective:

• FSA: fixed, bounded memory (only the current state — a fixed number of bits)
• PDA: finite but not fixed — the stack can grow without bound (unbounded memory)
• Key insight: regular languages are about bounded memory; context-free languages require unbounded memory (but with a specific LIFO structure)

1.11 PDAs and Compilers

PDAs are directly connected to how modern compilers work. A compiler is a program that translates source code (e.g., C, Python) into another language (e.g., machine code). It operates in several phases:

Regular languages are a proper subset of context-free languages

1. Lexical Analysis (Lexing): Breaks source code into tokens — the smallest meaningful units (keywords, identifiers, operators, etc.). The syntax of tokens is regular, so an FSA (or regular expression engine) performs this phase.
2. Syntax Analysis (Parsing): Verifies that the sequence of tokens conforms to the grammar of the programming language. Programming languages have nested structures (balanced brackets, function calls, arithmetic expressions), which are context-free. A PDA performs this phase.
3. Semantic Analysis: Checks type correctness, scope rules, etc.
4. Code Generation and Optimization: Produces and optimizes the target code.

Why PDAs for parsing? Programming languages have constructs requiring matched/nested structures:

• {...} blocks in C/Java
• begin...end in Pascal
• Parenthesized arithmetic expressions
• Nested function calls

These are precisely the kinds of structures that PDAs can handle and FSAs cannot.

Lexical analysis uses FSAs because tokens (like identifiers, numbers, keywords) follow regular patterns. For example, a Pascal identifier matches the regular pattern <letter>(<letter>|<digit>)*, which is easily recognized by an FSA.

Syntax analysis uses PDAs because grammar rules like “an expression is a term, then an operator, then another expression — possibly parenthesized” are context-free.

“Context-free grammars have played a central role in compiler technology since the 1960s… There is an automaton-like notation, called the ‘pushdown automaton’, that also describes all and only the context-free languages.” — John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman

1.12 The Pumping Lemma for Context-Free Languages (Bar-Hillel Lemma)

Just as the Pumping Lemma for regular languages gives us a tool to prove that certain languages are not regular, there is an analogous tool for context-free languages.

1.12.1 Pumping Lemma for Regular Languages (Recap)

Pumping Lemma (FSA): If is a regular language, then there exists such that any with can be written as satisfying:

• (i.e., )
• for any

The contrapositive is the tool for proving non-regularity: if no such decomposition exists for some word in , then is not regular.

1.12.2 Bar-Hillel Lemma (Pumping Lemma for Context-Free Languages)

Bar-Hillel Lemma: If is a context-free language (recognized by a PDA), then there exists such that any with can be written as satisfying:

• (at least one of or is non-empty)
• (the “middle” portion is not too long)
• for any (pumping both and simultaneously keeps the string in )

Key difference from regular Pumping Lemma: In the regular case, we pump a single segment . In the context-free case, we pump two segments ( and ) simultaneously — they must be pumped by the same number of repetitions .

The intuition comes from parse trees (Chomsky normal form). In a sufficiently tall parse tree, some non-terminal must repeat. The two “arms” hanging from the two occurrences of yield the two pumpable segments and .

Bar-Hillel intuition: a repeated nonterminal creates two pumpable branches

1.12.3 Contrapositive: Proving Non-Context-Freeness

Bar-Hillel Lemma (Corollary): If for any there exists with such that for every decomposition with and , there exists with , then is not context-free (cannot be recognized by any PDA).

The two-player game formulation:

Player 1 (Adversary)	Player 2 (You)
Picks any	Choose with
Picks any split with and	Find such that

You win (and is not context-free) if you can always find a defeating .

1.12.4 Classic Example:

Claim: is not recognized by any PDA.

Proof sketch: Let . Choose (with ). For any decomposition with and :

The distance from the first to the last is , but . Therefore cannot span all three symbol types simultaneously — it can contain at most two types of symbols (only ’s, only ’s, only ’s, or ’s and ’s, or ’s and ’s).

In every case, pumping with creates a string where at least one count is wrong:

• If contains only ’s: pumping adds more ’s but no ’s or ’s, giving .
• If contains only ’s: pumping gives .
• If contains only ’s: pumping gives .
• If spans ’s and ’s: pumping adds ’s and ’s but not ’s, giving an unbalanced string not in .
• If spans ’s and ’s: pumping adds ’s and ’s but not ’s, same problem.

In all cases, . Therefore is not context-free.

1.13 Beyond PDAs: The Limits of Context-Free Languages

Not all languages are context-free. The language is a canonical example of a language that lies beyond the power of PDAs. To recognize it, you would need to count three quantities simultaneously, but a stack can only maintain one linear count at a time.

To recognize such languages, we need an even more powerful model: the Turing Machine, which has a full read/write tape (not just a stack). The stack is a destructive memory — once a symbol is popped, it is gone. A tape is persistent — reading does not destroy.

The hierarchy of languages mirrors the hierarchy of machines:

• Regular languages — recognized by FSAs
• Context-free languages — recognized by PDAs (stack memory)
• Context-sensitive and more — recognized by Turing Machines (tape memory)

---

2. Definitions

• Pushdown Automaton (PDA): A computational model consisting of a finite control unit, an input tape, and an unbounded stack. Formally a 7-tuple . PDAs recognize exactly the class of context-free languages.
• Deterministic Pushdown Automaton (DPDA): A PDA where (1) for all (at most one transition at each step), and (2) implies for all (no conflict between input-reading and -transitions).
• Nondeterministic PDA: A PDA where may contain multiple possible transitions. The PDA accepts if some sequence of choices leads to acceptance.
• Stack: A last-in, first-out (LIFO) data structure used by a PDA as its main memory. Supports two operations: push (add to top) and pop (remove from top).
• Stack Alphabet (): The finite set of symbols that may appear on the PDA’s stack. Typically includes the bottom-of-stack marker .
• Bottom-of-Stack Symbol (): A special symbol placed at the bottom of the PDA’s stack initially. It is never removed and never duplicated. When is on top, the stack is effectively empty.
• Input Alphabet (): The finite set of symbols that the PDA reads from its input tape. Distinct from conceptually, though they may share symbols.
• Transition Function (): The function specifying PDA moves. A transition means: in state , reading (or ) from input and from the stack top, move to state and replace with string .
• -move: A PDA transition of the form that does not consume any input symbol. The PDA changes state and modifies the stack “spontaneously,” without reading the next character.
• -rule (DPDA condition): If there is an -transition from state with stack top , then there must be no input-reading transition from the same state with the same stack top . This ensures determinism.
• Configuration: A triple representing a complete “snapshot” of a PDA: current state , unread input , and stack contents (top to bottom). Also called a “PDA instantaneous description.”
• Transition Between Configurations (): A single computation step. if ; or if .
• Reflexive Transitive Closure (): means there is a sequence of zero or more steps from configuration to .
• Acceptance by Final State: A string is accepted if for some and . The stack content at the end is irrelevant.
• Acceptance by Empty Stack: A string is accepted if for some state (not necessarily in ). For DPDAs, these two acceptance modes are not equivalent.
• Context-Free Language (CFL): A language recognized by a pushdown automaton, or equivalently, generated by a context-free grammar. Every regular language is context-free, but not vice versa.
• Pumping Lemma (Regular Languages): If is regular, there exists such that every with has a split with , , and for all .
• Bar-Hillel Lemma (Pumping Lemma for CFLs): If is a context-free language, there exists such that every with has a split with , , and for all .
• Compiler: A program that translates source code in one language (e.g., C) into another language (e.g., machine code), typically via multiple phases: lexical analysis, syntax analysis, semantic analysis, and code generation.
• Lexical Analysis (Lexing): The first phase of compilation; breaks source code into tokens (keywords, identifiers, operators). Uses FSAs (regular languages) to recognize token patterns.
• Syntax Analysis (Parsing): The second phase of compilation; checks that the sequence of tokens conforms to the language grammar and constructs a parse tree. Uses PDAs (context-free languages) to handle nested language structures.
• Token: The smallest meaningful unit in a programming language (e.g., an identifier sum, an operator +, a keyword if). Recognized by lexical analysis.
• Parse Tree (Syntax Tree): A tree structure built during syntax analysis that represents the grammatical structure of the source code. Leaf nodes are tokens; internal nodes are grammar rules.
• Abstract Syntax Tree (AST): A simplified parse tree that represents the logical structure of the source code, used in semantic analysis, optimization, and code generation.
• Prefix-Free Language: A language where no string in is a proper prefix of another string in . Languages accepted by a DPDA via empty stack must be prefix-free.

---

3. Formulas

• PDA formal definition: where
• Transition notation: — read from input (or for spontaneous), pop from stack, push
• Push onto stack: replace top with — write
• Pop top : replace top with — write
• Leave stack unchanged: replace top with — write
• DPDA condition 1: for all , ,
• DPDA condition 2: for all , ,
• Configuration: where , (remaining input), (stack, top first)
• Transition (input symbol): when
• Transition (-move): when
• Acceptance by final state: for some ,
• Language recognized:
• Pumping Lemma (regular): regular s.t. with , split , , ,
• Bar-Hillel Lemma (CFL): context-free s.t. with , split , , ,
• Contrapositive (Bar-Hillel): is not CFL if , with such that splits with and : with

---

4. Practice

4.1. Construct a DPDA for (Lab 6, Task 1)

Build a DPDA that recognizes the language — strings of ’s followed by exactly ’s.

Click to see the solution

Key Concept: For each read, push two stack symbols (so you accumulate stack symbols for ’s). Then pop one stack symbol per . When all ’s are consumed and the stack holds only , the ratio is satisfied.

DPDA for aⁿb²ⁿ

1. PDA specification:

   • States: (start), (reading ’s), (reading ’s), (accepting)
   • Stack alphabet:

2. Transitions:

   Transition	Notation	Meaning
   		First : push two ’s
   		Each subsequent : push two more ’s (net: replace top with , adding two)
   		First : pop one
   		Each subsequent : pop one
   		All ’s consumed; accept

   Note on the push step: When reading with on top, we replace with — effectively, we keep the existing and add two more on top, so the stack grows by two per . Equivalently, since each should add two symbols: we replace (adding two) which matches the ratio.

3. Trace for input (, ):

   • : stack =
   • : stack =
   • : stack =
   • : ACCEPT

4. Trace for input (, ):

   • : stack =
   • : stack = (net +2: adds two)
   • : stack =
   • : stack =
   • : stack =
   • : stack = — (ERROR: stack underflow — wrong, recheck)

   Correction: Let’s recount. For : push 2 for first (stack = ), then replace top with for second : stack = (4 ’s? No — with top replaced by gives — that’s 3 ’s + ). We need symbols for .

   Revised approach: A cleaner strategy: for each , push two ’s unconditionally. Use a separate state to push the second .

   Transition	Notation	Meaning
   		First : push first
   		Spontaneous: push second
   		Subsequent (first push)
   …	…	…

   Simplest correct approach: For each , push two ’s by using a helper state:

   • States: (start), (just read , need to push second ), (ready to read or ), (reading ’s), (accepting)

   Transition	Notation	Meaning
   		First : push one
   		Push second (spontaneous)
   		Another : push first of two ’s
   		Start reading ’s: pop one
   		Each : pop one
   		Stack empty: accept

Answer: The DPDA using a helper state to push two ’s per , then popping one per , recognizes .

4.2. Construct a DPDA for Arithmetic Expression Parentheses (Lab 6, Homework 1)

Construct a DPDA that recognizes the language of well-formed parentheses of arithmetic expressions (binary operations). The alphabet is , where represents terms and is the binary operator.

Examples in the language: (a + a), ((a) + (a + a)), ((a + a)) The language consists of syntactically valid arithmetic expressions with parenthesized subexpressions.

Click to see the solution

Key Concept: This problem is about recognizing a simple expression grammar. The core constraint is that parentheses must be balanced: each ( must have a matching ), properly nested. The and symbols are essentially “filler” that don’t affect balancing.

DPDA skeleton for balanced parentheses in arithmetic expressions

Simplification: For the purpose of DPDA construction, the key property is that the parentheses must be balanced. The and symbols just need to appear in valid positions within the grammar. We model this by tracking open parentheses on the stack.

Grammar (informally):

• An expression is: a term, or ( expression ), or expression + expression

For a simple DPDA approach tracking only parenthesis balance:

1. States: (processing), (accepting)

   • Stack alphabet: where marks an open (

2. Transitions (loops on ):

   Notation	Meaning
   	Open (: push (stack was empty)
   	Open ( inside another: push
   	Close ): pop matching
   	Read term : no stack change
   	Read term inside parentheses: no stack change
   	Read operator outside parentheses: no stack change
   	Read operator inside parentheses: no stack change

3. Accept: : — balanced.

4. Trace for :

   • : stack =
   • : stack =
   • : stack =
   • : stack =
   • : stack =
   • : ACCEPT

Answer: The DPDA tracks parenthesis balance via the stack, accepting when all parentheses are matched and the input is fully consumed.

4.3. Construct a DPDA for (Lab 6, Task 2)

Build a DPDA that recognizes over the alphabet .

(The string consists of a non-empty string over , followed by a string over , followed by the center marker , followed by , followed by .)

Click to see the solution

Key Concept: Push all symbols of (using stack symbols for , for ) and then all symbols of (using for , for ). When appears, switch to pop mode: first pop (matching reversed), then pop (matching reversed).

1. PDA specification:
   • States: (pushing ), (pushing ), (popping ), (popping ), (accepting)
   • Stack alphabet:
2. Phase 1 — Push (state , loops):
   • ;
   • ;
   • ;
3. Transition to -push phase (state ): On reading the first or symbol, switch to :
   • ; ; ;
4. Phase 2 — Push (state , loops):
   • ;
   • ;
5. Pivot on ( or if empty):
   • ; (top is a -symbol: switch to pop- phase)
   • ; (no was pushed, skip to pop- phase: )
6. Phase 3 — Pop (state , loops):
   • ; (match , )
   • Transition to pop- phase when hitting an -symbol: on when top is or : ;
7. Phase 4 — Pop (state , loops):
   • ; (match , )
8. Accept: :

Answer: The DPDA with phases for pushing , pushing , popping , and popping (with as the pivot) recognizes .

4.4. Construct a DPDA for Balanced Brackets and Parentheses (Lab 6, Task 3)

Build a DPDA that recognizes the language of nested and balanced brackets and parentheses over the alphabet .

Examples of strings in the language: (([])())(), (())[] Examples NOT in the language: ([(]))()(), ([)]

Click to see the solution

Key Concept: Use the stack to track open delimiters. When ( is seen, push a marker for parenthesis. When [ is seen, push a marker for bracket. When ) is seen, pop the top and check it is (matching parenthesis). When ] is seen, pop and check it is (matching bracket). Accept when the input is exhausted and the stack holds only .

DPDA for balanced parentheses and brackets

Note: A key challenge is that ([)] must be rejected — the closing symbols must match the most recently opened one. The stack’s LIFO property enforces this naturally.

1. PDA specification:

   • States: (start, processing), (accepting)
   • Stack alphabet: where marks ( and marks [

2. Transitions (all loops on except the final accept):

   Notation	Meaning
   	Open ( on empty stack: push
   	Open ( with on top: push
   	Open ( with on top: push
   	Open [ on empty stack: push
   	Open [ with on top: push
   	Open [ with on top: push
   	Close ) with on top: pop (matched!)
   	Close ] with on top: pop (matched!)

3. Accept: : — all matched, stack has only .

4. Rejection (implicitly): If ) is read but (not ) is on top, there is no defined transition, so the PDA gets stuck and rejects. This correctly rejects strings like ([)].

5. Trace for input :

   • : stack =
   • : stack =
   • : stack =
   • : stack =
   • : ACCEPT

Answer: The DPDA above recognizes the language of nested and balanced brackets and parentheses over .

4.5. Construct a DPDA for (Lab 6, Task 4)

Build a DPDA that recognizes , where is the number of occurrences of character in string . In other words, is the set of all strings over with equal numbers of ’s and ’s (in any order).

Click to see the solution

Key Concept: Unlike where all ’s come first, here ’s and ’s can be interleaved in any order. We use the stack as a counter: push for each seen (when stack contains only or ’s), and push for each seen (when stack contains only or ’s). When the top symbol and the input symbol cancel (an arrives while the top is , or a arrives while the top is ), pop the top instead. This is a net balance counter.

1. PDA specification:

   • States: (processing), (accepting)
   • Stack alphabet:
   • on the stack means “more ’s seen so far”; means “more ’s seen so far”

2. Transitions (all loops on ):

   Notation	Meaning
   	Read , stack balanced so far: push (now +1 )
   	Read , currently have excess ’s: push more
   	Read , currently have excess ’s: cancel one
   	Read , stack balanced so far: push (now +1 )
   	Read , currently have excess ’s: push more
   	Read , currently have excess ’s: cancel one

3. Accept: : — all cancelled out, stack holds : counts equal; accept.

4. Trace for input :

   • : stack = (1 excess )
   • : stack = (cancelled)
   • : stack = (1 excess )
   • : stack = (cancelled)
   • : ACCEPT

5. Trace for input (should reject since ):

   • : stack =
   • : stack =
   • : stack =
   • Input exhausted; stack is (not just ); no -accept transition applies. REJECT

Answer: The DPDA above uses the stack as a signed counter to recognize .

4.6. Construct a DPDA for (Lab 6, Task 5)

Build a DPDA that recognizes .

Click to see the solution

Key Concept: The string has the form — an outer -layer, an inner -layer, a matching inner -layer, and a matching outer -layer. Use the stack in two phases:

DPDA for aⁿbᵐaᵐbⁿ

• Phase 1 (outer ’s): Push copies of for the leading ’s.
• Phase 2 (inner ’s): Push copies of for the leading ’s (on top of the ’s).
• Phase 3 (inner ’s): Pop one per (matching the inner ’s with inner ’s).
• Phase 4 (outer ’s): Pop one per (matching the outer ’s with outer ’s).

1. States: (reading outer ’s), (reading inner ’s), (reading inner ’s), (reading outer ’s), (accepting)

2. Transitions:

   Transition	Notation	Meaning
   		First outer : push
   		More outer ’s: push
   		First inner : push on top of ’s
   		More inner ’s: push
   		First inner : pop one
   		More inner ’s: pop
   		First outer : pop one (all ’s gone)
   		More outer ’s: pop
   		All matched: accept

3. Trace for input is too short (minimum: ):

   Trace for ():

   • : stack =
   • : stack =
   • : stack =
   • : stack =
   • : ACCEPT

Answer: The DPDA with phases for outer ’s, inner ’s, inner ’s, and outer ’s recognizes .

4.7. Prove That Is Not Context-Free (Tutorial 6, Example 1)

Use the Bar-Hillel Lemma (Pumping Lemma for context-free languages) to prove that is not a context-free language.

Click to see the solution

Key Concept: In , the number of ’s, ’s, and ’s must all be equal. The Bar-Hillel Lemma pumps two segments simultaneously, but any two-segment window of size in can cover at most two types of symbols. Pumping creates an imbalance in at least one count.

1. Assume for contradiction that is context-free. Let be the pumping length given by the Bar-Hillel Lemma.

2. Choose the word . Note .

3. Consider any split with and .

4. Restrict where can lie: The distance from the first to the last is characters. Since , the window cannot span all three types of symbols simultaneously. It can cover:

   • Only ’s, or only ’s, or only ’s, or
   • ’s and ’s (but not ’s), or ’s and ’s (but not ’s)

5. Pump with (pump up): Consider . In every case:

   • If contains only ’s: pumping adds ’s but no ’s or ’s. The result has more ’s than ’s and ’s. .
   • If contains only ’s: pumping adds ’s but no ’s or ’s. .
   • If contains only ’s: pumping adds ’s but no ’s or ’s. .
   • If spans ’s and ’s: pumping adds more ’s and ’s but no extra ’s. .
   • If spans ’s and ’s: pumping adds more ’s and ’s but no extra ’s. .

6. Conclusion: In every case, . The Bar-Hillel Lemma is violated. Therefore is not context-free.

Answer: is not a context-free language.

4.8. Construct a DPDA for (Tutorial 6, Example 2)

Construct a Deterministic Pushdown Automaton (DPDA) that recognizes , and trace the computation on the input .

Click to see the solution

Key Concept: Use the stack to count ’s: push one per read, then pop one per read. If the stack holds only exactly when all ’s are consumed, the counts matched.

DPDA trace machine for aⁿbⁿ

1. PDA specification:

   • States: (start), (reading ’s), (reading ’s), (accepting)
   • Stack alphabet:
   • Input alphabet:

2. Transitions:

   Transition	Notation	Meaning
   		Read first ; push on top of
   		Read additional ’s; push each time
   		Read first ; pop one
   		Read additional ’s; pop one each time
   		Input exhausted; on top means all ’s were matched; accept

3. Verification that this is a DPDA:

   • Each entry has exactly one output: condition 1 satisfied.
   • The -transition uses stack top . No input-reading transition from has on top: condition 2 satisfied.

4. Trace for input :

   Step	State	Remaining Input	Stack	Rule
   1				: push
   2				: push
   3				: pop
   4				: pop
   5				: accept
   6				ACCEPT

   Full configuration sequence:

Answer: The DPDA with states (accepting) and the transitions above recognizes .

4.9. Construct a DPDA for (Tutorial 6, Example 3)

Construct a DPDA that recognizes .

Click to see the solution

Key Concept: Push one per before the . The single is a pivot — it signals to switch from push mode to pop mode. After the , pop one per on the right side. Equal stacks before and after means equal -counts.

1. PDA specification:

   • States: (start, push phase), (pop phase, after ), (accepting)
   • Stack alphabet:

2. Transitions:

   Transition	Notation	Meaning
   		First before : push
   		Each subsequent before : push
   		Read the : keep stack unchanged, switch to pop phase
   		Each after : pop one
   		All ’s matched; accept

3. Trace for input :

   • : stack =
   • : stack = (unchanged)
   • : stack =
   • : ACCEPT

4. Trace for input :

   • : stack =
   • : stack =
   • : stack =
   • : stack =
   • : stack =
   • : ACCEPT

Answer: The DPDA with states (accepting) and the transitions above recognizes .

4.10. Construct a DPDA for (Tutorial 6, Example 4)

Construct a DPDA that recognizes , where denotes the reverse of and is a special separator symbol. The input alphabet is .

Click to see the solution

Key Concept: Push every symbol of onto the stack (using distinct symbols for and for ). When the center is seen, switch to pop mode. Then match each symbol of against the stack. Since is the reverse of , the stack contents should match from top to bottom.

1. PDA specification:

   • States: (push phase), (pop phase), (accepting)
   • Stack alphabet: where represents and represents

2. Transitions:

   Push phase (, self-loops — push symbols of ):

   Notation	Meaning
   	First : push
   	First : push
   	Subsequent with on top: push
   	Subsequent with on top: push
   	Subsequent with on top: push
   	Subsequent with on top: push

   Pivot (on reading , move , keep stack unchanged):

   Notation	Meaning
   	was empty: switch to pop mode
   	seen with on top: switch to pop mode
   	seen with on top: switch to pop mode

   Pop phase (, self-loops — match ):

   Notation	Meaning
   	Read , top is : match, pop
   	Read , top is : match, pop

   Accept: : — all matched, accept.

3. Trace for input (so , ):

   • : stack =
   • : stack =
   • : stack = (unchanged)
   • : stack =
   • : stack =
   • : ACCEPT

Answer: The DPDA with states (accepting) and the transitions above recognizes .